public class test {
    // leetcode 542.01矩阵
    class Solution {
        public int[] dx = {0,0,1,-1};
        public int[] dy = {1,-1,0,0};
        public Queue<int[]> queue;
        public int[][] nums;
        public int row;
        public int col;
        public int[][] updateMatrix(int[][] mat) {
            row = mat.length;
            col = mat[0].length;
            nums = new int[row][col];
            queue = new LinkedList<>();
            //所有元素初始化为-1(除了0)
            //'-1'代表该位置未找到最短路径
            for(int i = 0;i < row;i++){
                for(int j = 0;j < col;j++){
                    nums[i][j] = -1;
                    //以所有0作为'超级原点'
                    //方便为路径点赋值
                    if(mat[i][j] == 0){
                        nums[i][j] = 0;
                        queue.add(new int[]{i,j});
                    }
                }
            }
            int len = 1;
            while(!queue.isEmpty()){
                int size = queue.size();
                for(int i = 0;i < size;i++){
                    int[] t = queue.poll();
                    for(int j =0;j<4;j++){
                        int x = t[0] + dx[j];
                        int y = t[1] + dy[j];
                        if(x >= 0 && x < row && y >= 0 && y < col && nums[x][y] == -1){
                            nums[x][y] = len;
                            queue.add(new int[]{x,y});
                        }
                    }
                }
                len++;
            }
            return nums;
        }
    }
    // leetcode 675.为高尔夫比赛砍树
    class Solution {
        public int num = 0;
        public int row;
        public int col;
        public int[] dx = { 0, 0, 1, -1 };
        public int[] dy = { 1, -1, 0, 0 };
        public int[] trees;
        public int[][] nums;
        public HashMap<Integer, int[]> map;
        public int xxn = 0;
        public int yyn = 0;

        public int cutOffTree(List<List<Integer>> forest) {
            row = forest.size();
            col = forest.get(0).size();
            // 每次不能重复的走走过的路
            // trees用于存储所有树,为了后续将它们进行排序
            trees = new int[row * col];
            nums = new int[row][col];
            map = new HashMap<>();
            int k = 0;
            int start = forest.get(0).get(0);
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    int n = forest.get(i).get(j);
                    // 代表当前元素为一个树
                    // 将这棵树的下标存入map中
                    if (n > 1) {
                        map.put(n, new int[] { i, j });
                        trees[k++] = n;
                    }
                    nums[i][j] = n;
                }
            }
            // 将树从小到大进行排序
            trees = Arrays.copyOfRange(trees, 0, k);
            Arrays.sort(trees);
            for (int i = 0; i < trees.length; i++) {
                int[] t = map.get(trees[i]);
                int n = findTree(t[0], t[1]);
                if (n == -1) {
                    return -1;
                }
                num += n;
            }
            return num;
        }

        // 走迷宫问题,传入起点和目标位置
        public int findTree(int keyX, int keyY) {
            boolean[][] count = new boolean[row][col];
            if (keyX == xxn && keyY == yyn) {
                return 0;
            }
            int n = 0;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[] { xxn, yyn });
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] t = queue.poll();
                    for (int j = 0; j < 4; j++) {
                        int xx = t[0] + dx[j];
                        int yy = t[1] + dy[j];
                        // 1. 保证xx和yy都合法
                        // 2. 保证[xx,yy]有路
                        // 3. 不能走重复的路
                        if (xx >= 0 && xx < row && yy >= 0 && yy < col && nums[xx][yy] > 0 && !count[xx][yy]) {
                            // 找到目标位置,返回当前步数
                            if (xx == keyX && yy == keyY) {
                                xxn = xx;
                                yyn = yy;
                                nums[xx][yy] = 1;
                                return n + 1;
                            }
                            queue.add(new int[] { xx, yy });
                            count[xx][yy] = true;
                        }
                    }
                }
                n++;
            }
            return -1;
        }
    }
}
